Primitive Root

定义 Definition

primitive root（原根）：数论中的概念。对正整数 (n)，若存在整数 (g) 使得 (g) 与 (n) 互素，并且 (g) 的幂 (g^1, g^2, \dots) 在模 (n) 意义下能生成所有与 (n) 互素的剩余类（即形成模 (n) 的乘法群的生成元），则称 (g) 是 模 (n) 的一个原根。
常见情形：当 (n) 为奇素数 (p) 时，原根一定存在。

发音 Pronunciation (IPA)

/ˈprɪmɪtɪv ruːt/

例句 Examples

A primitive root modulo 7 is 3.
模 7 的一个原根是 3。

If (g) is a primitive root modulo (p), then every nonzero residue modulo (p) can be written as (g^k \bmod p) for some integer (k).
如果 (g) 是模素数 (p) 的原根，那么模 (p) 的每个非零剩余都可以表示为某个 (g^k \bmod p)。

词源 Etymology

primitive 源自拉丁语 primitivus，含义是“最初的、原始的”；root 本义为“根”。在数学里，“root（根）”常用来指“基础来源/生成因素”。因此 primitive root 可理解为“最基本、能生成全部元素的‘根’（生成元）”。

相关词 Related Words

• Generator
• Modulo
• Congruence
• Coprime
• Residue
• Cyclic
• Order
• Euler's Totient Function
• Discrete Logarithm
• Finite Field

文学与经典著作中的用例 Literary Works

• An Introduction to the Theory of Numbers（Hardy & Wright，《数论导引》）：在讨论模素数的乘法群与循环群结构时频繁使用 primitive root。
• A Classical Introduction to Modern Number Theory（Ireland & Rosen）：在初等数论与代数数论的衔接处讲解原根及其存在性。
• Elementary Number Theory（David M. Burton，《初等数论》）：以入门方式介绍原根、指数表与离散对数的关系。